package leetcode_400;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨 
 *LexicographicalNumbers_386 给定一个正整数n 输出其1-n的字典排序
 *describe:AC 90% 回溯法 用boolean返回值剪枝
 *2018年7月12日 下午8:41:43
 */
public class LexicographicalNumbers_386 {
	 List<Integer> res;
	 int n;
	public static void main(String[] args) {
		LexicographicalNumbers_386 test=new LexicographicalNumbers_386();
		List<Integer> temp=test.lexicalOrder(13);

	}
	
	 public List<Integer> lexicalOrder(int n) {
		 this.n=n;
		 this.res=new ArrayList<Integer>();
		 if(n<1)
			 return this.res;
		 for(int i=1;i<10;++i) {
			 help(i);
		 }
	     return this.res;
	 }
	 
	 public boolean help(int now) {
		 if(now>this.n)
			 return false;
		 this.res.add(now);
		 int temp=now*10;
		 for(int i=0;i<=9;++i) {
			 if(!help(temp+i))
				 return true;
		 }
		 return true;
	 }

}
